\parskip 12 pt
\parindent 0 pt
\magnify {1100}
\centerline{\bf CS154, PROBLEM SET 8, SOLUTIONS}

8.7

We may rely on Church's thesis so that this is just a problem about
Turing machines.

(a) This is essentially problem 8.3, which is solved in the text.

(b) This is equivalent to determining if an r.e. set is non-empty.
Since this is a non-trivial property, Rice's theorem says that it
is undecidable.

(c) Suppose that we can solve this problem.  Then we can specialize
it so that one of the languages is empty.  Then we can determine
whether any r.e. set is empty.  Since this is a non-trivial property,
Rice's theorem says that it is undecidable.  This is a contradiction;
therefore, the given problem is undecidable.

I. Is it decidalbe whether the language generated by an
arbitrary CFG is regular?  I don't know.

II. It is decidable whether an arbitrary Turing machine, $M$, accepts
an arbitrary string, $L$, after at most 1983 steps.  To decide, just
run the machine for 1983 steps and see if it has accepted the string.

III.  Yes.  See the first two paragraphs of page 179 to see that there
exists a Turing machine that tells whether there exists a unique god.